package com.atcumt.Carl.LinkedList;


public class LinkedList01 {

    /**
     * 移除链表元素
     * 方法：额外创建一个虚拟节点，指向头
     */
    public ListNode removeElements(ListNode head, int val) {

        if (head == null) {
            return head;
        }

        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;
        ListNode cur = head;
        while (cur != null) {
            if (cur.val == val) {
                pre.next = cur.next; // 删除节点
            } else {
                pre = cur;
            }
            cur = cur.next; // 遍历节点
        }
        return dummy.next;
    }

    /**
     * 翻转链表
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre; // pre 指针指向新的头结点
    }

    /**
     * 两两交换链表节点
     * head = list[i]  pre = list[i - 1]
     */
    public ListNode swapPairs(ListNode head) {
        ListNode dummy = new ListNode(-1, head);
        ListNode pre = dummy;

        while (pre.next != null && pre.next.next != null) {
            ListNode tmp = head.next.next;
            head.next.next = head; // 开始交换
            pre.next = head.next;
            head.next = tmp;
            pre = head;
            head = head.next; // 遍历
        }
        return dummy.next;
    }

    /**
     * 删除链表倒数第 N节点
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode fast = dummy;
        ListNode slow = dummy;

        // 快指针先走 N步
        while (n-- > 0) {
            fast = fast.next;
        }
        // 快慢指针一起走
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        // 删除倒数第 N个节点
        slow = slow.next.next;
        return dummy.next;
    }

    /**
     * 环形链表
     */
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (slow == fast) {
                break;
            }
        }
        // 无环
        if (fast == null || fast.next == null) {
            return null;
        }

        // 有环
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}
